package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

/**
 * @author Dennis Li
 * @date 2020/6/13 22:10
 */
public class Palindrome_234 {

    public boolean isPalindromeEasy(ListNode head) {
        ListNode slow = head, fast = head;
        int len = 0;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            len++;
        }

        // 奇数个结点
        if (fast != null) slow = slow.next;
        slow = reverse(slow);

        while (len > 0) {
            if(head.val != slow.val)
                return false;
            head = head.next;
            slow = slow.next;
            len--;
        }

        return true;
    }

    public boolean isPalindrome(ListNode head) {
        // 用两个指针 -- 一个一次走一步，一个一次走两步.
        // 第二个结点恰好走了第一个结点的两倍路程
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 核心思想：切成两半，将后半段反转，再进行比较
        // 偶数结点
        if (fast.next != null) slow = slow.next;
        cutList(head, slow);
        ListNode reverse = reverse(slow);
        return isEqual(head, reverse);
    }

    private void cutList(ListNode head, ListNode cutNode) {
        while (head.next != cutNode) {
            head = head.next;
        }
        head.next = null;
    }

    // 如何反转链表，还需要加强
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    private boolean isEqual(ListNode p1, ListNode p2) {
        while (p1 != null && p2 != null) {
            if (p1.val != p2.val)
                return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }
}
